/*
提交链接：https://leetcode.cn/problems/find-if-path-exists-in-graph/submissions/573450979
1971. 寻找图中是否存在路径-简单
完成日期：2024/10/17
并查集
*/

class UnionFind {
public:
    UnionFind(int size) {
        parent.resize(size);
        for (int i = 0; i < size; i++) {
            parent[i] = i; // 初始化每个节点的父节点为自己
        }
    }
    int find(int node) {
        if (parent[node] != node) {
            parent[node] = find(parent[node]); // 路径压缩
        }
        return parent[node];
    }
    void unionNodes(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU != rootV) {
            parent[rootU] = rootV; // 将两个节点的根合并
        }
    }
private:
    vector<int> parent; // 存储每个节点的父节点
};
class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        // 如果源和目标相同，直接返回 true
        if (source == destination) return true;
        // 初始化并查集
        UnionFind uf(n);
        // 合并所有边
        for (const auto& edge : edges) {
            uf.unionNodes(edge[0], edge[1]);
        }
        // 检查 source 和 destination 是否在同一个连通分量
        return uf.find(source) == uf.find(destination);
    }
};